/*
 *  Copyright 2008-2009 NVIDIA Corporation
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */


#include <algorithm>
#include <vector>
#include <stdio.h>

#include <cusp/blas.h>
#include <cusp/csr_matrix.h>
#include <cusp/transpose.h>

#include <cusp/detail/host/reference/csr.h>

extern "C" {
#include <patoh.h>
    int PaToH_Part(PPaToH_Parameters pargs, int _c, int _n, int _nconst, int useFixCells,
                   int *cwghts, int *nwghts, int *xpins, int *pins, float *targetweights,
                   int *partvec, int *partweights, int *cut);
};

namespace cusp
{
namespace graph
{
namespace detail
{
namespace host
{
static void wrapPaToH(int _c, int _n,
                      int *xpins, int *pins,
                      int *cwghts, int *nwghts,
                      int _k, int _nconst,
                      int *partvec,
                      int *partwghts, double imbal, int cuttype, int *cut_p) {

    PaToH_Parameters       args;
#ifdef SETRANDSEED
    static int patohseed=-1;

    if (patohseed==-1) {
        struct timeval tp;

        gettimeofday(&tp, NULL);

        patohseed = tp.tv_sec;
    } else
        ++patohseed;
#endif

    PaToH_Initialize_Parameters(&args, cuttype, PATOH_SUGPARAM_DEFAULT);
    args._k = _k;

    if (PaToH_Alloc(&args, _c, _n, _nconst, cwghts, nwghts, xpins, pins))
        throw cusp::runtime_exception("error in allocating memory for PaToH");

#ifdef SETRANDSEED
    args.seed = patohseed;
#endif
    args.final_imbal = imbal;
    args.init_imbal = imbal * 2.0;

    PaToH_Part(&args, _c, _n, _nconst, 0, cwghts, nwghts,
               xpins, pins, NULL, partvec, partwghts, cut_p);

    PaToH_Free();
}

template<class ArrayType1, class ArrayType2>
int PaToH(size_t n_row, size_t n_col, size_t n_entries,
          const ArrayType1& Ap, const ArrayType1& Ai, const ArrayType2& Ax,
          size_t Nconst, const ArrayType2& Cwghts, const ArrayType2& Nwghts,
          const size_t K, const int cuttype, const double imbal,
          ArrayType1& partv)
{
    /*PaToH's arguments*/
    int cut;
    int _n = n_col;
    int _c = n_row;
    int _k = K;
    int _nconst = Nconst;
    int *xpins = (int *) thrust::raw_pointer_cast(&Ap[0]);
    int *pins  = (int *) thrust::raw_pointer_cast(&Ai[0]); 

    partv.resize(_c);
    int *partv_p = (int *) thrust::raw_pointer_cast(&partv[0]);
    cusp::array1d<int, cusp::host_memory> partwghts(_k*_nconst, 0);
    int *partwghts_p = (int *) thrust::raw_pointer_cast(&partwghts[0]);

    cusp::array1d<int, cusp::host_memory> cwghts(_c*_nconst, 0);
    cusp::array1d<int, cusp::host_memory> nwghts(_n, 0);

    if ( !Cwghts.empty() ) {
 	int size = cwghts.size();
        for( int i = 0; i < size; i++ )
            cwghts[i] = (int)ceil(Cwghts[i]);
    } else
        cusp::blas::fill(cwghts, 1);

    if ( !Nwghts.empty() ) {
 	int size = nwghts.size();
        for( int i = 0; i < size; i++ )
            nwghts[i] = (int)ceil(Nwghts[i]);
    } else
        cusp::blas::fill(nwghts, 1);

    int *cwghts_p = thrust::raw_pointer_cast(&cwghts[0]);
    int *nwghts_p = thrust::raw_pointer_cast(&nwghts[0]);

    if( (cuttype != PATOH_CUTPART) && (cuttype != PATOH_CONPART) )
        throw cusp::invalid_input_exception("cuttype should be either CON or CUT");

    wrapPaToH(_c,  _n,
              xpins , pins,
              cwghts_p, nwghts_p,
              _k, _nconst,
              partv_p,
              partwghts_p, imbal, cuttype, &cut);

    return cut;
}

template <class MatrixType, class ArrayType1, class ArrayType2>
size_t partition(const MatrixType& A,
		 size_t m, 
                 size_t num_parts,
                 const ArrayType1& Cwghts,
		 ArrayType2& part,
                 cusp::graph::patoh)
{
    typedef typename MatrixType::index_type IndexType;
    typedef typename MatrixType::value_type ValueType;

    size_t edgecut;
    int nconst = 1;
    int cuttype = PATOH_CONPART;
    ValueType imbal = 0.03;

    cusp::array1d<ValueType,cusp::host_memory> Nwghts;

    cusp::array1d<IndexType,cusp::host_memory> csc_column_offsets(A.num_cols+1);
    cusp::array1d<IndexType,cusp::host_memory> csc_row_indices(A.num_entries);
    cusp::array1d<ValueType,cusp::host_memory> csc_values(A.values);

    csr_tocsc( 	int(A.num_rows), int(A.num_cols), 
		thrust::raw_pointer_cast(&A.row_offsets[0]),
		thrust::raw_pointer_cast(&A.column_indices[0]),
		thrust::raw_pointer_cast(&A.values[0]),
		thrust::raw_pointer_cast(&csc_column_offsets[0]),
		thrust::raw_pointer_cast(&csc_row_indices[0]),
		thrust::raw_pointer_cast(&csc_values[0]) );

    edgecut = PaToH( A.num_rows, A.num_cols, A.num_entries,
	   	     csc_column_offsets, csc_row_indices, csc_values,
	   	     nconst, Cwghts, Nwghts,
	   	     num_parts, cuttype, imbal,
	   	     part );

    printf(" [edgecut: (%lu) %4.4f%%]\n", edgecut, 100* (double) edgecut / (double) A.num_entries);
    return edgecut;
}

} // end namespace host
} // end namespace detail
} // end namespace graph
} // end namespace cusp

